Konspekt ten dotyczy wykorzystania schematu Hornera do obliczania wartości wielomianu oraz obliczania dziesiętnej wartości liczb zapisanych w różnych systemach pozycyjnych.
Temat: Schemat Hornera i jego zastosowanie.
Czas trwania zajęć: 2 godz.
Cel ogólny: uczeń zna schemat Hornera i potrafi obliczyć wartość wielomianu iteracyjnie i rekurencyjnie.
Cele operacyjne: a) wiadomości: - umie podać różnice między iteracją a rekurencją - wie, jak wygląda postać ogólna wielomianu - rozumie znaczenie optymalizacji algorytmu b) umiejętności - potrafi zastosować schemat Hornera do obliczeń - potrafi napisać program obliczający wartość dowolnego wielomianu iteracyjnie i rekurencyjnie - potrafi prawidłowo interpretować znaczenie komunikatów oprogramowania - potrafi ocenić złożoność algorytmu
Środki dydaktyczne: stanowiska komputerowe, środowisko FreePascal, kalkulator, tablica
Metoda pracy: problemowa, dyskusji, ćwiczeń
Forma pracy: częściowo praca zbiorowa jednolita oraz praca samodzielna przy komputerze
Przebieg zajęć:
I. Część wprowadzająca
Nauczyciel przedstawia uczniom zagadnienie omawiane na lekcji.
Przypomina postać ogólną wielomianu: w(x) = a0xn + a1xn-1 + a2xn-2 + ... + an-1x + an
Nauczyciel pyta uczniów, jak obliczamy wartość wielomianu.
Zapis działań, jakie należy wykonać w celu obliczenia wartości wielomianu: w = 3x4 + 2x3 + x2 - 4x + 2, dla x= 3
Nauczyciel podaje przykłady zastosowania umiejętności obliczania wartości wielomianu:
1) Wielomiany to podstawowe funkcje w informatyce, gdyż wartości większości innych funkcji są obliczane jako wartości odpowiednich wielomianów.
2) Zapis liczby dziesiętnej w dowolnym systemie pozycyjnym przy ustalonej podstawie np. 2. Jest to wielomian, w którym współczynniki mogą przyjmować tylko określone wartości (np. 0, 1), a w miejscu zmiennej xwystępuje podstawa systemu.
Przykład: (1011011)2 = 1*26+ 0*25 + 1*24 + 1*23 + 0*22+ 1*21 + 1*20
II. Część główna
Nauczyciel prosi o określenie złożoności tego sposobu obliczania wartości wielomianu.
Uczniowie podają, ile mnożeń i dodawań należy wykonać wykorzystując ten sposób obliczeń dla przykładu wielomianu w - 10 i 4).
Nauczyciel podaje wzór ogólny mnożeń i n dodawań.
A. Schemat Hornera
Nauczyciel wskazuje na inny sposób obliczania wartości wielomianu (wyprowadzając wzór): dla wielomianu w z przykładu: w = (((3x + 2)x + 1)x - 4)x + 2 dla postaci ogólnej wielomianu: w(x) = (...((a0x + a1)x + a2)x + ... + an-1)x + an
Nauczyciel zwraca uwagę uczniów na prostotę obliczania wartości wielomianu tym sposobem (np. na kalkulatorze bez wykorzystywania pamięci).
Nauczyciel prosi uczniów o określenie złożoności tego sposobu na przykładzie wielomianu w, i ogólnie - n mnożeń i n dodawań.
Nauczyciel i uczniowie wspólnie formułują wniosek: Obliczając wartość wielomianu tym sposobem zmniejszymy ilość mnożeń - jest to sposób efektywniejszy i okazuje się, że jest on najbardziej efektywny.
Uczniowie odpowiadają na pytanie: Dlaczego to jest tak ważne?
Mnożenie zajmuje procesorowi bardzo dużo czasu, więc wszelkie ograniczanie tego działania w jakimkolwiek algorytmie zwiększa jego szybkość w znacznym stopniu (mnożenie jest operacją czasochłonną i eliminacja zbędnych mnożeń jest jednym z podstawowych problemów optymalizacji algorytmów).
Interpretacja schematu Hornera w sposób iteracyjny.
Uczniowie wskazują na operacje, które się powtarzają (można je wykorzystać do zbudowania pętli - jako działanie wi = wi-1*x+ ai, dla i = 1, ..., n - w przypadku programowania można ten wzór zapisać, wykorzystując operator podstawiania, jako w = w*x + ai, dla i = 1, ..., n).
Wspólne zapisanie schematu Hornera w postaci schematu blokowego.
Dane: n - liczba naturalna - stopień wielomianu, a0, a1, ..., an - liczby rzeczywiste - współczynniki wielomianu, x - liczba rzeczywista - argument, dla którego będzie obliczana wartość wielomianu
Użyte zmienne:
i - liczba naturalna - licznik kontrolujący kolejne współczynniki, w - liczba rzeczywista - wartość kolejnych obliczeń wykonywanych w pętlach
Wynik: wartość wielomianu (ostatnia wartość zmiennej w) obliczona według schematu Hornera
Zapisanie schematu Hornera w postaci funkcji w języku Pascal (przypomnienie, że współczynniki wielomianu najłatwiej zapisać w pamięci komputera w postaci tablicy):
function wartosc:real; var i:byte; w:real; begin w:=a[0]; for i:=1 to n do w:=w*x+a[i]; wartosc:=w; end;
Nauczyciel prosi o dokończenie programu i sprawdzenie poprawności działania.
Interpretacja schematu Hornera w sposób rekurencyjny.
Nauczyciel przypomina, że algorytmy iteracyjne da się przedstawić w sposób rekurencyjny, i odwrotnie.
Zapisanie kolejnych iteracji w postaci wzorów: w0 = a0 w1 = w0*x + a1 w2 = w1*x + a2 ... wn = wn-1*x + an
oraz wzoru rekurencyjnego: w0 = a0 wn = wn-1*x + an
Na podstawie wzoru tworzymy funkcję rekurencyjną w języku Pascal.
function wartoscrek(k:byte):real; begin if k=0 then wartoscrek:=t[0] else wartoscrek:=wartoscrek(k-1)*x+a[k]; end;
B. Zastosowanie schematu Hornera
Obliczanie wartości wielomianu.
Nauczyciel poleca uczniom uruchomienie programu Kalkulator (widok podstawowy) i obliczenie wartości przykładowego wielomianu, wykorzystując schemat Hornera oraz działania mnożenia i dodawania/odejmowania.
Dziesiętna reprezentacja liczb zapisanych w różnych systemach pozycyjnych.
Nauczyciel prosi o obliczenie wartości dziesiętnej liczby zapisanej w systemie dwójkowym, wykorzystując schemat Hornera (kolejne cyfry - współczynniki wielomianu, argument - liczba 2 - podstawa systemu). (((((1*2 + 0)*2 + 1)*2 + 1)*2 + 0)*2 + 1)*2 + 1 =
Tak można obliczyć dziesiętną wartość liczby w dowolnym systemie (przy podstawach większych od 10 problemem może być zamiana współczynników).
Nauczyciel zauważa, że w przypadku systemu dwójkowego, można jeszcze bardziej zoptymalizować ten program – mnożenie współczynnika przez 2 można zastąpić dodawaniem.
III. Część podsumowująca
Uczniowie odpowiadają na pytania: Co to jest schemat Hornera? Dlaczego jest tak ważny? Do czego można go wykorzystać?
Nauczyciel zadaje uczniom pracę domową: Odnaleźć w książce do matematyki schemat Hornera, dotyczący dzielenia wielomianu przez dwumian i przeanalizować go. Zastanowić się, jak napisać program dotyczący schematu Hornera bez użycia tablic.
Opracował: Maciej Milczarek
|